Clustering merupakan salah satu bagian dari unsupervised learning. Clustering memiliki tujuan untuk membagi data ke dalam beberapa kelompok berdasarkan kemiripan antar data. cluster (kelompok) yang baik adalah cluster yang memiliki kemiripan yang besar antar anggota clusternya dan memiliki perbedaan yang signifikan dengan anggota cluster yang berbeda. Clustering dapat diterapkan dalam berbagai bidang seperti segmentasi pasar, cluster profiling, data spatial dll. Metode clustering sangat beragam, namun bila ingin dikelompokkan secara general berdasarkan metodenya clustering dapat dibagi menjadi beberapa kelompok seperti gambar dibawah.
pada gambar diatas bisa dilihat bahwa metode clustering dapat dibagi menjadi 4 metode. Pada artikel ini akan dibahas salah satu algoritma yang menggunakan metode kerapatan (density-based) yaitu DBSCAN.
Untuk menggunakan DBSCAN pada R anda perlu menginstall package dbscan terlebih dahulu.
install.packages("dbscan")
Berikut beberapa packages yang digunakan pada artikel ini.
library(dplyr)
# clustering libs
library(dbscan)
library(factoextra)
library(cluster)
# visualization libs
library(ggplot2)
library(leaflet)
library(ggthemes)
library(fishualize)
algoritma Density-based Spatial Clustering of Application with Noise (DBSCAN) merupakan metode clustering yang berbasis kepadatan (density-based) dari posisi amatan data dengan prinsip mengelompokkan data yang relatif berdekatan. DBSCAN sering diterapkan pada data yang banyak mengandung noise, hal ini dikarenakan metode DBSCAN tidak akan memasukkan data yang dianggap noise kedalam cluster manapun.
Algoritma DBSCAN memerlukan dua parameter input sebelum melakukan proses clustering yaitu epsilon dan minPts. Epsilon merupakan jarak maksimal antara dua amatan dalam satu cluster yang diizinkan, dan minPts adalah banyaknya data minimal dalam jarak epsilon agar terbentuk suatu cluster. Metode jarak yang digunakan dalam Algoritma DBSCAN adalah jarak Euclidian. Sepasang amatan dikatakan bertetangga apabila jarak antara dua amatan tersebut kurang dari sama dengan nilai epsilon. Selain epsilon dan MinPts ada beberapa terminologi lain dalam metode DBSCAN yaitu :
directly density-reachable : observasi q berhubungan langsung dengan p, jika p adalah core point dan q merupakan tetangga dari p dalam jangkauan epsilon.density-reachable : observasi q dan x dalam satu cluster namun x bukan tetangga dari q dalam jangkauan epsilon.core point : core point merupakan observasi yang memiliki jumlah tetangga lebih dari sama dengan dari MinPts pada jangkauan Eps.border point : border point memiliki tetangga lebih sedikit dari Minpts namun ia merupakan tetangga dari core point.outlier/noise point : observasi yang bukan border points atau core points.secara sederhana cara kerja DBSCAN adalah sebagai berikut :
1. tentukan nilai Minpts dan epsilon (eps) yang akan digunakan.
2. Pilih data awal “p” secara acak.
3. Hitung jarak antara data “p” terhadap semua data menggunakan Euclidian distance.
4. Ambil semua amatan yang density-reachable dengan amatan “p”.
5. Jika amatan yang memenuhi nilai epsilon lebih dari jumlah minimal amatan dalam satu gerombol maka amatan “p” dikategorikan sebagai core points dan gerombol terbentuk.
6. Jika amatan “p” adalah border points dan tidak ada amatan yang density-reachable dengan amatan “p”, maka lanjutkan pada amatan lainnya.
7. Ulangi langkah 3 sampai 6 hingga semua amatan diproses.
untuk menggunakan metode DBSCAN pada R anda harus menginstall packges dbscan terlebih dahulu. Data yang digunakan adalah data multishape dari packages factoextra, pada data ini terdapat 3 variabel yaitu x, y, dan shape. untuk proses pembuatan cluster, variabel yang akan digunakan hanya x dan y.
data("multishapes")
multishapes <- multishapes[,1:2]
head(multishapes)
## x y
## 1 -0.8037393 -0.8530526
## 2 0.8528507 0.3676184
## 3 0.9271795 -0.2749024
## 4 -0.7526261 -0.5115652
## 5 0.7068462 0.8106792
## 6 1.0346985 0.3946550
Secara visual data multishape dapat dilihat seperti plot dibawah. Pada plot tersebut terlihat bahwa kerapatan antar data membentuk beberapa bentuk seperti lingkaran dan persegi panjang.
ggplot(data = multishapes, aes(x = x, y = y)) +
geom_point(col = "firebrick4") +
theme_pander()
Tahap awal sebelum melakukan clustering adalah memilih nilai nilai minpts dan epsilon (eps). Untuk memilih nilai minpts dan eps yang tepat bisa menggunakan function kNNdistplot dari packages dbscan. Ide utama dari fungsi ini adalah menghitung jarak rata2 untuk setiap data ke k tetangga terdekatnya (nearest neighbors). Nilai dari K ditentukan oleh user yang nantinya akan digunakan sebagai minPts pada proses clustering. Selanjutnya rata rata jarak tersebut diplot secara ascending untuk mendapatkan “knee” yang menunjukkan nilai optimal dari eps berdasarkan K yang ditentukan.
kNNdistplot(multishapes, k = 4)
abline(h = 0.15, col = "red", lty = 2)
Berdasarkan plot diatas dengan menggunakan K = 4 didapat jarak yang optimal yaitu sekitar 0.15. Nilai 0.15 didapat dari posisi “knee” yang terbentuk pada plot. dengan menggunakan hasil plot diatas maka nilai Eps yang digunakan pada proses clustering adalah 0.15 dengan minPts 4. Tahap selanjutnya adalah pembuatan cluster menggunakan function dbscan dengan parameter yang sudah didapat.
db_clust <- dbscan(multishapes, eps = 0.15, minPts = 4)
db_clust
## DBSCAN clustering for 1100 objects.
## Parameters: eps = 0.15, minPts = 4
## The clustering contains 5 cluster(s) and 29 noise points.
##
## 0 1 2 3 4 5
## 29 411 405 105 99 51
##
## Available fields: cluster, eps, minPts
Hasil clustering dari data multishape dengan 1100 observasi adalah 5 cluster dan sebanyak 29 data diidentifikasi sebagai noise. Cluster 1 merupakan cluster dengan anggota cluster terbanyak sedangkan cluster 5 merupakan cluster dengan anggota cluster paling sedikit. Hasil cluster yang sudah dibentuk dapat dilakukan visualisasi agar terlihat pola dari cluster yang didapat.
multishapes <- multishapes %>%
mutate(clust = db_clust$cluster,
clust = ifelse(clust==0,"Noise",clust))
ggplot(data =multishapes, aes(x = x, y = y)) +
geom_point(aes(col = as.factor(clust))) +
theme_pander() +
labs(col = "Cluster")
Dari hasil visualisasi diatas bisa dilihat bahwa cluster yang dihasilkan dbscan dapat mengelompokkan data sehingga bisa menangkap beberapa bentuk dari data. Noise yang terdeteksi pada data terlihat menyebar, hal ini dikarenakan data noise tidak berhasil ditangkap eps yang ditentukan.
DBSCAN merupakan metode clustering yang sangat sensitif terhadap perubahan parameter. Perbedaan kecil pada parameter yang ada (minPts, Eps) dapat menghasilkan cluster yang berbeda. Sebagai contoh pada data multishapes yang sebelumnya digunakan apabila nilai eps diubah yang awalnya 0.15 menjadi 0.2 akan menghasilkan cluster yang berbeda
db_clust <- dbscan(multishapes[,1:2], eps = 0.2, minPts = 4)
db_clust
## DBSCAN clustering for 1100 objects.
## Parameters: eps = 0.2, minPts = 4
## The clustering contains 4 cluster(s) and 20 noise points.
##
## 0 1 2 3 4
## 20 820 106 102 52
##
## Available fields: cluster, eps, minPts
dengan mengubah parameter eps yang semula 0.15 menjadi 0.2 maka hasil cluster yang terbentuk menjadi 4 dan noise yang dihasilkan menjadi semakin berkurang yaitu 20. Bila diamati lebih detail lagi cluster 1 mengalami penambahan anggota cluster secara signifikan, yang semula 411 menjadi 820. Pola cluster yang sudah dibuat dapat divisualisasikan agar dapat melihat perbedaan dengan proses clustering sebelumnya.
multishapes <- multishapes %>%
mutate(clust = db_clust$cluster,
clust = ifelse(clust==0,"Noise",clust))
ggplot(data =multishapes, aes(x = x, y = y)) +
geom_point(aes(col = as.factor(clust))) +
theme_pander() +
labs(col = "Cluster")
Dari hasil visualisasi diatas bisa dilihat bahwa cluster 1 yang baru menggabungkan cluster 1 dan 2 pada proses cluster sebelumnya, serta noise yang awalnya berada disekitar cluster 1 menjadi anggota cluster 1.
Metode DBSCAN sering diimplemtasikan pada data spatial hal ini dikarenakan dimensi dari data spasial yang cukup sederhana yaitu longitide dan latitude. Data yang digunakan pada artikel ini adalah data kebakaran di Australia pada awal tahun 2020. Anda dapat mengunduh data lengkapnya pada link berikut
nasa_fire <- readr::read_csv('data_input/nasa_fire.csv')
head(nasa_fire)
Data nasa_fire memiliki 3 variabel yaitu latitude, longitude, dan confidence. Nilai confidence berkisar dari 0 hingga 100 yang menunjukkan tingkat keyakinan kebakaran terjadi. Sebelum masuk pada proses pembuatan cluster, data nasa_fire akan divisualisasikan dalam bentuk peta menggunakan packages leaflet.
leaflet(data = nasa_fire) %>%
addTiles() %>%
setView(lng = 133.7751,lat = -25.2744,zoom = 4) %>%
addCircleMarkers(lng = ~longitude,
lat = ~latitude,
radius =1)
Dari visualisasi diatas bisa dilihat bahwa titik kebakaran menggerombol pada beberapa area, dan beberapa titik kebakaran berada jauh dari kerumunan yang ada. Tahap selanjutnya adalah menentukan nilai MinPts dan Eps yang optimum dengan menggunakan fungsi KNNdistplot.
kNNdistplot(nasa_fire[,1:2], k = 10)
abline(h= 0.8, col = "red", lty = 3) #0.8
dengan menggunkan k = 10 maka didapat nilai eps sebesar 0.8 berdasarkan “knee” yang terbentuk dari plot. Selanjutnya proses pembuatan cluster menggunakan fungsi
dbscan dengan parameter yang sudah didapat yaitu minPts = 10 dan eps = 0.8.
nasa_clust <- dbscan(nasa_fire[,1:2], eps = 0.8, minPts = 10)
nasa_clust
## DBSCAN clustering for 25937 objects.
## Parameters: eps = 0.8, minPts = 10
## The clustering contains 44 cluster(s) and 251 noise points.
##
## 0 1 2 3 4 5 6 7 8 9 10 11
## 251 18333 603 159 47 367 10 16 17 203 847 47
## 12 13 14 15 16 17 18 19 20 21 22 23
## 242 656 907 1060 247 28 53 23 69 27 78 57
## 24 25 26 27 28 29 30 31 32 33 34 35
## 51 15 11 661 54 17 150 60 15 19 20 195
## 36 37 38 39 40 41 42 43 44
## 124 32 32 16 13 24 12 11 58
##
## Available fields: cluster, eps, minPts
Clustering yang dilakukan menghasilkan 44 cluster dan 251 data noise. Cluster dengan jumlah anggota terbanyak dimiliki cluster 1 dengan 18333 anggota cluster dan cluser 43 dan 26 sebagai cluster dengan anggota cluster paling sedikit yaitu 11. Hasil Cluster dapat divisualisasikan dalam peta untuk melihat persebaran cluster yang dibentuk.
# membuat kolom baru untuk cluster
nasa_fire <- nasa_fire %>%
mutate(clust = nasa_clust$cluster)
# membuat pallet color untuk setiap cluster
pallet <- fishualize::fish(n = length(unique(nasa_fire$clust)), option = "Bryaninops_natans")
pal <- colorFactor(pallet, domain = unique(nasa_fire$clust))
# visualisasi cluser tanpa data noise
leaflet(data = nasa_fire[nasa_fire$clust !=0,]) %>%
addTiles() %>%
setView(lng = 133.7751,lat = -25.2744,zoom = 4) %>%
addCircleMarkers(lng = ~longitude,
lat = ~latitude,
radius =1,
color = ~pal(clust))
visualisasi diatas tanpa menggunakan data noise agar cluster yang sudah dibentuk bisa terlihat lebih jelas. Berdasarkan visualisasi data diatas kebakaran paling padat didaerah tenggara Australia.
DBSCAN merupakan algoritma clustering yang menggunakan metode density-based. Tidak seperti algoritma K-means yang menggunakan partitioning method, DBSCAN tidak memerlukan jumlah cluster sebagai inputan melainkan epsilon dan minPts. Epsilon merupakan jarak maksimal antara dua amatan dalam satu cluster yang diizinkan, dan minPts adalah banyaknya data minimal dalam jarak epsilon agar terbentuk suatu cluster. Kelebihan dari metode ini adalah dapat menangkap cluster yang memiliki bentuk serta bisa mendeteksi noise yang ada pada data. Kekurangan dari metode ini adalah tidak cocok untuk data yang memiliki tingkat kerapatan beragam, DBSCAN juga tidak cocok untuk data dengan dimensi yang besar, selain itu DBSCAN sangat sensitif terhadap perubahan nilai pada parameter.